/*  time_kdtree.cpp
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cassert>
#include<cmath>

using namespace std;

#include <time.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <stdarg.h>
#include <unistd.h>
#include <limits.h>
#include <string.h>
#include <math.h>

#include <CGAL/basic.h>
#include <CGAL/Kd_tree.h>

#include <CGAL/Cartesian.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Search_traits_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
#include <CGAL/Orthogonal_k_neighbor_search.h>
#include <CGAL/Euclidean_distance.h>
#include <CGAL/Fuzzy_iso_box.h>
#include <CGAL/Fuzzy_sphere.h>

#include <vector>
#include <iostream>

typedef CGAL::Cartesian<double>                         R;
typedef R::Point_2                                      Point_2;
typedef R::Segment_2                                    Segment_2;
typedef R::Iso_rectangle_2                              Iso_rectangle_2;
typedef R::FT                                           FT;
typedef R::Circle_2                                     Circle_2;

typedef CGAL::Creator_uniform_2<FT, Point_2>            Creator;
typedef CGAL::Plane_separator<FT>                       Separator;
typedef CGAL::Search_traits_2<R>             Traits;
typedef CGAL::Euclidean_distance<Traits>               Distance;
typedef CGAL::Orthogonal_k_neighbor_search<Traits>        Neighbour_search;
typedef CGAL::Fuzzy_iso_box<Traits> Fuzzy_box;
typedef CGAL::Fuzzy_sphere<Traits>                   Fuzzy_circle;
typedef CGAL::Kd_tree<Traits> Tree;
typedef std::vector<Traits::Point_d>                      Vector;
typedef std::vector<Point_2>                            Query_vector;

static struct timeval __start, __stop;
static inline void TimerStart() { gettimeofday(&__start,NULL); }
static inline void TimerStop()  { gettimeofday(&__stop,NULL); }
static inline double TimerElapsed() {
  return (double)(__stop.tv_sec - __start.tv_sec) + 
    ((double)__stop.tv_usec - 
     (double)__start.tv_usec)/1000000;
}


Point_2 readPoint(istream & in) {
  double x,y;
  in >> x >> y;
  return Point_2(x,y);
}

bool processQuery(Tree & tree) {
  size_t acc = 0;
  size_t qs;
  cin >> qs;
  TimerStart();
  while(qs--) {
    vector<Point_2> lst;
    Point_2 p1 = readPoint(cin);
    Point_2 p2 = readPoint(cin);
    Iso_rectangle_2 rect(p2,p1);
    Fuzzy_box range((rect.min)(),(rect.max)());
    tree.search(back_inserter(lst),range);
    acc += lst.size();
  }
  TimerStop();
  cout << "Time for count: " << TimerElapsed() << "s" << endl;
  cout << "Checksum: " << acc << endl;
  return false;
}

int main(int argc, char ** argv) {
  if(argc!=2) {
    cout << "usage: " << argv[0] << " <input>" << endl;
    return 0;
  }

  ifstream input(argv[1]);
  if(!input.is_open()) {
    cout << "Error opening file: " << argv[1] << endl;
    return -1;
  }

  size_t points;
  input >> points;
  Tree tree;
  for(size_t i=0;i<points;i++) {
    Point_2 p = readPoint(input);
    tree.insert(p);
  }
  
  //cout << "This tree has " << tree.size() << endl;
  processQuery(tree);
  return 0;
}

